package algorithm.niuke;

import java.util.LinkedList;
/*
出入口换算成门
迷宫问题==》门匹配问题
遇门找钥匙==>拿钥匙就可以往回走
*/
/*
0 b 1 C 1
0 1 a 0 A
0 c 0 0 B
0 1 0 0 1
0 1 0 0 1
0 1 1 1 1
*/
import java.util.Scanner;

public class 迷宫寻路 {
    public static int[] size = new int[2];
    public static char[][] map = new char[105][105];

    public static void main(String[] args) {
        input(size, map);
        boolean findStart = false;
        int result = -1;
        for (int i = 0; i < size[0]; i++) {
            for (int j = 0; j < size[1]; j++) {
                if (map[i][j] == '2') {
                    findStart = true;
                    result = bfs(i, j);
                    break;
                }
            }
            if (findStart) {
                break;
            }
        }
        System.out.println(result);
    }

    public static class Node {
        int x;
        int y;
        int keys;
        int step;

        Node(int x, int y, int keys, int step) {
            this.x = x;
            this.y = y;
            this.keys = keys;
            this.step = step;
        }
    }

    public static int bfs(int startIIndex, int startJIndex) {
        LinkedList<Node> queue = new LinkedList<Node>();
        int[][][] visit = new int[size[0]][size[1]][1025];
        queue.offer(new Node(startIIndex, startJIndex, 0, 0));
        int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;
            int keys = node.keys;
            int step = node.step;
            //System.out.println(x + " " + y + " " + keys + " " + step);
            if (x < 0 || y < 0 || x >= size[0] || y >= size[1]) {
                continue;// 越界
            }
            if (map[x][y] == '3') {
                return step;// 结束
            }
            if (visit[x][y][keys] == 1 || map[x][y] == '0') {// 已经访问过
                continue;
            }
            if ((map[x][y] >= 'A' && map[x][y] <= 'Z') && ((1 << (map[x][y] - 'A')) & (keys)) == 0) {// 有门无钥匙
                continue;
            }
            visit[x][y][keys] = 1;
            if ((map[x][y] >= 'a' && map[x][y] <= 'z')) {
                keys = keys | (1 << (map[x][y] - 'a'));// 带上钥匙
            }
            for (int i = 0; i < 4; i++) {
                queue.offer(new Node(x + dir[i][0], y + dir[i][1], keys, step + 1));
            }
        }
        return -1;
    }

    static void input(int[] size, char[][] map) {
        Scanner cin = new Scanner(System.in);
        String sizeStr = cin.nextLine();
        String[] sizeStrs = sizeStr.split(" ");
        size[0] = Integer.valueOf(sizeStrs[0]);
        size[1] = Integer.valueOf(sizeStrs[1]);
        for (int row = 0; row < size[0]; row++) {
            String rowStr = cin.nextLine();
            int index = 0;
            for (char ch : rowStr.toCharArray()) {
                map[row][index++] = ch;
            }
        }
    }

    static void print(int[] size, char[][] map) {
        for (int i = 0; i < size[0]; i++) {
            for (int j = 0; j < size[1]; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }
}